/**
 * Priority Queue (优先队列) 实现
 * 
 * 优先队列是一种特殊的队列，其中每个元素都有一个优先级。
 * 元素按照优先级顺序出队，优先级高的元素先出队。
 * 
 * 时间复杂度：
 * - 插入: O(log n)
 * - 删除: O(log n)
 * - 查看最高优先级元素: O(1)
 * 
 * 空间复杂度: O(n)
 */

class PriorityQueue {
  constructor(compareFunction = (a, b) => a - b) {
    // TODO: 初始化优先队列
    // this.heap = []
    // this.compare = compareFunction
  }

  /**
   * 获取父节点索引
   * @param {number} index - 当前节点索引
   * @returns {number} - 父节点索引
   */
  getParentIndex(index) {
    // TODO: 实现获取父节点索引逻辑
    // 1. 使用公式 (index - 1) / 2
    // 2. 使用Math.floor向下取整
  }

  /**
   * 获取左子节点索引
   * @param {number} index - 当前节点索引
   * @returns {number} - 左子节点索引
   */
  getLeftChildIndex(index) {
    // TODO: 实现获取左子节点索引逻辑
    // 1. 使用公式 2 * index + 1
  }

  /**
   * 获取右子节点索引
   * @param {number} index - 当前节点索引
   * @returns {number} - 右子节点索引
   */
  getRightChildIndex(index) {
    // TODO: 实现获取右子节点索引逻辑
    // 1. 使用公式 2 * index + 2
  }

  /**
   * 交换两个元素
   * @param {number} index1 - 第一个元素索引
   * @param {number} index2 - 第二个元素索引
   */
  swap(index1, index2) {
    // TODO: 实现交换逻辑
    // 1. 使用临时变量交换两个元素
  }

  /**
   * 向上调整堆
   * @param {number} index - 当前节点索引
   */
  heapifyUp(index) {
    // TODO: 实现向上调整逻辑
    // 1. 如果当前节点是根节点，返回
    // 2. 获取父节点索引
    // 3. 比较当前节点和父节点
    // 4. 如果需要交换，交换并递归向上调整
  }

  /**
   * 向下调整堆
   * @param {number} index - 当前节点索引
   */
  heapifyDown(index) {
    // TODO: 实现向下调整逻辑
    // 1. 获取左右子节点索引
    // 2. 找到优先级最高的子节点
    // 3. 比较当前节点和最高优先级子节点
    // 4. 如果需要交换，交换并递归向下调整
  }

  /**
   * 插入元素
   * @param {*} element - 要插入的元素
   */
  enqueue(element) {
    // TODO: 实现插入逻辑
    // 1. 将元素添加到堆的末尾
    // 2. 向上调整堆
  }

  /**
   * 删除最高优先级元素
   * @returns {*} - 被删除的元素
   */
  dequeue() {
    // TODO: 实现删除逻辑
    // 1. 如果堆为空，返回null
    // 2. 保存根节点元素
    // 3. 将最后一个元素移到根节点
    // 4. 向下调整堆
    // 5. 返回保存的元素
  }

  /**
   * 查看最高优先级元素
   * @returns {*} - 最高优先级元素
   */
  peek() {
    // TODO: 实现查看逻辑
    // 1. 如果堆为空，返回null
    // 2. 返回根节点元素
  }

  /**
   * 检查优先队列是否为空
   * @returns {boolean} - 是否为空
   */
  isEmpty() {
    // TODO: 实现检查是否为空逻辑
    // 1. 检查堆的长度是否为0
  }

  /**
   * 获取优先队列大小
   * @returns {number} - 大小
   */
  size() {
    // TODO: 实现获取大小逻辑
    // 1. 返回堆的长度
  }

  /**
   * 清空优先队列
   */
  clear() {
    // TODO: 实现清空逻辑
    // 1. 重置堆数组
  }

  /**
   * 检查堆是否有效
   * @returns {boolean} - 是否有效
   */
  isValid() {
    // TODO: 实现检查堆是否有效逻辑
    // 1. 遍历所有非叶子节点
    // 2. 检查每个节点是否满足堆性质
    // 3. 返回是否有效
  }

  /**
   * 获取所有元素
   * @returns {Array} - 所有元素的数组
   */
  toArray() {
    // TODO: 实现获取所有元素逻辑
    // 1. 返回堆的副本
  }

  /**
   * 查找元素索引
   * @param {*} element - 要查找的元素
   * @returns {number} - 元素索引，如果不存在返回-1
   */
  indexOf(element) {
    // TODO: 实现查找元素索引逻辑
    // 1. 遍历堆数组
    // 2. 找到匹配的元素
    // 3. 返回索引或-1
  }

  /**
   * 更新元素优先级
   * @param {*} oldElement - 旧元素
   * @param {*} newElement - 新元素
   * @returns {boolean} - 是否成功更新
   */
  updatePriority(oldElement, newElement) {
    // TODO: 实现更新优先级逻辑
    // 1. 找到旧元素的索引
    // 2. 如果找到，更新元素
    // 3. 重新调整堆
    // 4. 返回是否成功
  }
}

module.exports = PriorityQueue
